#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

 

示例 1：


输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trim-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

//类似与删除多个节点了
// 返回删除后的头节点
TreeNode* trimBST(TreeNode* root, int low, int high) {
    //如果为null
    if (!root)
        return root;

    if (root->val<low||root->val>high)
    {
        //删除逻辑
        if (root->left== nullptr)
            return root->right;
        else if (root->right== nullptr)
            return root->left;

        //如果左右都不为null
        else{
            //寻找柚子树的 最左边
            TreeNode* cur=root->right;

            while (cur->left)
            {
                cur=cur->left;
            }
            cur->left=root->left;
            root = root->right; // 返回旧root的右孩⼦作为新root
            return root;

        }



    }

    if (root->val>low)
       root->left=trimBST(root->left,  low,  high);

    if (root->val<high)
        root->right=trimBST(root->right,  low,  high);

    return root;


}
